package com.cuz.hot100;

import com.cuz.daileetcode.utils.ArrayUtils;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Q57insertInterval {
    public static void main(String[] args) {
        //[[1,3],[6,9]]
        //newInterval =
        //[2,5]
        int[][] ints2 = {{1, 3}, {6, 9}};
        int[] ints4 = {2, 5};
        int[][] insert = new Q57insertInterval().insert(ints2,ints4);
        System.out.println(Arrays.deepToString(insert));
//        int[][] ints = {{1, 2}, {3, 5}, {6, 7}, {8, 10}, {12, 16}};
//        int[] ints1 = {4, 8};
        //[[0,2],[3,3],[6,11]]
        //[9,15]
        //[[3,5],[12,15]]
        //[6,6]
        //[[0,2],[3,3],[6,11]]
        //[9,15]
        int[][] ints = {{1, 5}};
        int[] ints1 = {6, 8};
//        int[][] ints2 = insert1(ints, ints1);
        int[][] ints3 = insert2(ints, ints1);
//        ArrayUtils.print(ints2);
        ArrayUtils.print(ints3);
    }

    public static int[][] insert1(int[][] intervals, int[] newInterval) {
        if (intervals == null || intervals.length == 0 || intervals[0].length == 0) {
            return new int[][]{newInterval};
        }
        LinkedList<int[]> resList = new LinkedList<>();
        int minOfNew = newInterval[0];
        int maxOfNew = newInterval[1];
        boolean hasMerged = false;
        if (maxOfNew < intervals[0][0]) {
            resList.addAll(Arrays.asList(intervals));
            resList.addFirst(newInterval);
        } else if (minOfNew > intervals[intervals.length - 1][1]) {
            resList.addAll(Arrays.asList(intervals));
            resList.addLast(newInterval);
        } else {
            for (int index = 0; index < intervals.length; index++) {
                int[] interval = intervals[index];
                if (!hasMerged) {
                    if ((minOfNew >= interval[0] && minOfNew <= interval[1])
                            || (maxOfNew <= interval[1]) && (maxOfNew >= interval[0])
                            || (minOfNew <= interval[0] && maxOfNew >= interval[1])) {
                        int[] temp = new int[]{Math.min(interval[0], minOfNew),
                                Math.max(interval[1], maxOfNew)};
                        resList.add(temp);
                        hasMerged = true;
                    } else if (minOfNew > interval[1] && (index == intervals.length - 1 || maxOfNew <= intervals[index + 1][0])) {
                        resList.add(interval);
                        resList.add(newInterval);
                        hasMerged = true;
                    } else {
                        resList.add(interval);
                    }
                } else {
                    int[] lastInterval = resList.getLast();
                    if (lastInterval[1] >= interval[0]) {
                        lastInterval[1] = Math.max(lastInterval[1], interval[1]);
                        lastInterval[0] = Math.min(lastInterval[0], interval[0]);
                    } else {
                        resList.add(interval);
                    }
                }
            }
        }
        return resList.toArray(new int[resList.size()][2]);
    }

    private static boolean hasIntersect(int minOfNew, int maxOfNew, int[] interval) {
        return ((minOfNew >= interval[0] && minOfNew <= interval[1])
                || (maxOfNew <= interval[1]) && (maxOfNew >= interval[0])
                || (minOfNew <= interval[0] && maxOfNew >= interval[1]));
    }

    public static int[][] insert2(int[][] intervals, int[] newInterval) {
        if (intervals == null || intervals.length == 0 || intervals[0].length == 0) {
            return new int[][]{newInterval};
        }
        LinkedList<int[]> resList = new LinkedList<>();
        int minOfNew = newInterval[0];
        int maxOfNew = newInterval[1];
        boolean hasMerged = false;
        for (int index = 0; index < intervals.length; index++) {
            int[] interval = intervals[index];
            if (!hasMerged) {
                if (hasIntersect(minOfNew, maxOfNew, interval)) {
                    int[] temp = new int[]{Math.min(interval[0], minOfNew),
                            Math.max(interval[1], maxOfNew)};
                    resList.add(temp);
                    hasMerged = true;
                } else {
                    hasMerged = true;
                    if (minOfNew > interval[1]) {
                        resList.add(interval);
                        resList.add(newInterval);
                    } else {
                        resList.add(newInterval);
                        resList.add(interval);
                    }
                }
            } else {
                int[] last = resList.getLast();
                if (hasIntersect(last[0], last[1], interval)) {
                    last[0] = Math.min(last[0], interval[0]);
                    last[1] = Math.max(last[1], interval[1]);
                } else {
                    if (interval[1] < last[0]) {
                        resList.removeLast();
                        resList.addLast(interval);
                        resList.add(last);
                        continue;
                    }
                    resList.addLast(interval);
                }
            }
        }
        return resList.toArray(new int[resList.size()][2]);
    }

    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> resList = new ArrayList<>();

        int index = 0;
        int len = intervals.length;
        while(index<len && intervals[index][1]<newInterval[0]){
            resList.add(intervals[index]);
            index++;
        }
        while(index < len && intervals[index][0]<= newInterval[1]){
            //[[1,2],[3,5],[6,7],[8,10],[12,16]]
            //[4,8]
            //index = 1
            //[3,5] merge with [4,8]  ==>[3,8]

            newInterval[0] = Math.min(newInterval[0],intervals[index][0]);
            newInterval[1] = Math.max(newInterval[1],intervals[index][1]);
            index++;
        }
        resList.add(newInterval);
        while(index<len){
            resList.add(intervals[index]);
            index++;
        }
        return resList.toArray(new int[][]{});

    }
}
